Postfix to Prefix Conversion

Objective

Your goal is to convert a postfix expression (Reverse Polish Notation) into its equivalent prefix expression (Polish Notation) by building and traversing an expression tree.

Algorithm

1. Build the Expression Tree: Process the postfix expression from left to right using a stack.
   • When an operand (e.g., A, B) is found, create a single-node tree for it and push it onto the stack.
   • When an operator (e.g., +, *) is found, pop two trees from the stack. The first popped is the right child (T₂) and the second is the left child (T₁). Create a new tree with the operator as the root and push it back onto the stack.
2. Generate the Prefix String: After processing all tokens, the stack will hold the complete expression tree. Perform a preorder traversal (Root → Left → Right) on this tree to produce the final prefix expression.

Example

For the postfix expression A B + C *, the algorithm builds the following tree:

  *
   / \
  +   C
 / \
A   B

A preorder traversal yields the prefix expression: * + A B C.

I/O Format

Input

• Line 1: An integer N (1 ≤ N ≤ 1000), the number of tokens.
• Line 2: The postfix expression, with N tokens separated by spaces.

Token Rules

• Operands: Single uppercase letters (A-Z).
• Operators: The four binary operators: +, -, *, /.

Output

• A single line containing the corresponding prefix expression, with tokens separated by spaces.

Samples

Sample 1:

5

A B + C *

* + A B C

Sample 2:

7

A B C * + D /

/ + A * B C D

Sample 3:

7

A B + C D - *

* + A B - C D

Limitations